11115. Красивое число

Вам дано два множества, состоящих из ненулевых цифр.

В десятичной записи мы называем целое положительное число красивым, если оно содержит хотя бы одну цифру из каждого этих наборов.

Найдите наименьшее красивое число.

Вход. В первой строке даётся два целых числа n и m (1 ≤ n, m ≤ 9) – размеры первого и второго множества. Во второй строке даётся n различных цифр d₁, d₂, ..., d_n. В третьей строке даётся m различных цифр r₁, r₂, ..., r_m (1 ≤ d_i, r_i ≤ 9).

Выход. Выведите наименьшее красивое число.

Пример входа	Пример выхода
2 2 1 4 8 3	13

РЕШЕНИЕ

жадность

Анализ алгоритма

Если массивы d и r содержат одну и ту же цифру, то наименьшая из таких цифр будет ответом.

Иначе сортируем массивы d и r. Находим наименьшие цифры d[0] и r[0]. Составляем из них минимальное двузначное число. Это будет или d[0] * 10 + r[0] или r[0] * 10 + d[0].

Пример

Пусть d = {1, 3, 5, 7, 9}, r = {2, 3, 4, 5, 8, 9}. Наименьшей общей цифрой будет 3. Следовательно ответом будет число 3.

Пусть d = {1, 3, 5, 7, 9}, r = {2, 4, 6, 8}. Общих цифр нет. Наименьшими цифрами в массивах будут 1 и 2. Составляем из них наименьшее число 12, которое и будет ответом.

Реализация алгоритма

Объявим рабочие массивы.

vector<int> d, r;

int dc[10], rc[10];

Читаем входные данные.

scanf("%d %d", &n, &m);

Произведем сортировку подсчетом. Занесем в dc[x] количество раз, которое число x встречается в массиве d.

d.resize(n);

for (i = 0; i < n; i++)

{

scanf("%d", &d[i]);

dc[d[i]]++;

}

Занесем в rc[x] количество раз, которое число x встречается в массиве r.

r.resize(m);

for (i = 0; i < m; i++)

{

scanf("%d", &r[i]);

rc[r[i]]++;

}

Переберем цифры от 1 до 9. Если цифра i присутствует в обеих массивах, то выводим ответ – число i.

for (i = 1; i <= 9; i++)

if (dc[i] > 0 && rc[i] > 0)

{

printf("%d\n", i);

return 0;

}

Сортируем массивы.

sort(d.begin(), d.end());

sort(r.begin(), r.end());

Из наименьших цифр массивов d[0] и r[0] составляем минимальное двузначное число.

if (d[0] < r[0])

res = 10 * d[0] + r[0];

else

res = 10 * r[0] + d[0];

Выводим ответ.

printf("%d\n", res);